package leetcode101.dynamic_planning;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code27
 * @Description 646. 最长数对链
 * 给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
 *
 * 现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
 *
 * 给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
 *
 *  
 *
 * 示例：
 *
 * 输入：[[1,2], [2,3], [3,4]]
 * 输出：2
 * 解释：最长的数对链是 [1,2] -> [3,4]
 *  
 *
 * 提示：
 *
 * 给出数对的个数在 [1, 1000] 范围内。
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-22 8:39
 */
public class Code27 {
    public static void main(String[] args) {
        int[][] nums = new int[][] {{-1,1},{-2,7},{-5,8},{-3,8},{1,3},{-2,9},{-5,2}};
        System.out.println(findLongestChain(nums));
    }

    public static int findLongestChain(int[][] pairs) {
        int nums = pairs.length;
        int[] dp = new int[nums + 1];
        int maxLocal = Integer.MIN_VALUE;
        int ans = Integer.MIN_VALUE;
        dp[1] = 1;
        quickSort(pairs, 0, nums - 1);
        for (int i = 2; i < dp.length; i++) {
            for (int j = 1; j < i; j++) {
                if (pairs[i - 1][0] > pairs[j - 1][1] && dp[j] > maxLocal) {
                    maxLocal = dp[j];
                }
            }
            dp[i] = maxLocal + 1;
            ans = Math.max(dp[i], ans);
        }
        return Math.min(ans, dp[1]);
    }

    public static void quickSort(int[][] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high);
            quickSort(arr, low, pivot - 1);
            quickSort(arr, pivot + 1, high);
        }
    }

    public static int partition(int[][] arr, int low, int high) {
        int[] temp = arr[low];
        while (low < high) {
            while (low < high && arr[high][1] >= temp[1]) {
                high--;
            }
            arr[low] = arr[high];
            while (low < high && arr[low][1] <= temp[1]) {
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low] = temp;
        return low;
    }
}
/*
按结束时间排序再dp
 */